#include <bits/stdc++.h>
using namespace std;
class Solution {

pair<int, int> findrank(vector<int> &a, int x) {
    return make_pair(lower_bound(a.begin(), a.end(), x) - a.begin(), upper_bound(a.begin(), a.end(), x) - a.begin());
}

pair<int, int> findrank(vector<int> &a, vector<int> &b, int x) {
    auto p1 = findrank(a, x), p2 = findrank(b, x);
    return make_pair(p1.first + p2.first, p1.second + p2.second);
}

bool inbound(pair<int, int> p, int x) {
    return (p.first <= x && x < p.second);
}

int findprev(vector<int> &a, int x) {
    int p = lower_bound(a.begin(), a.end(), x) - a.begin();
    printf("%d\n", p);
    if (p)
        return a[p-1];
    else
        return -0x7fffffff-1;
    
}

int findnext(vector<int> &a, int x) {
    int p = upper_bound(a.begin(), a.end(), x) - a.begin();
    if (p < a.size())
        return a[p];
    else
        return 0x7fffffff;
}

int findprev(vector<int> &a, vector<int> &b, int id) {
    return max(findprev(a, a[id]), findprev(b, a[id]));
}

int findnext(vector<int> &a, vector<int> &b, int id) {
    return min(findnext(a, a[id]), findnext(b, a[id]));
}

public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> &a = nums1, &b = nums2;
        // if (a.size() < b.size()) swap(a, b);
        // printf("%d %d\n", a[0], b[0]);
        int n = a.size() + b.size();
        pair<int, int> tar((n-1)/2, n/2);
        if (a.size() == 0)
            return ((double)b[tar.first] + b[tar.second]) / 2;
        if (b.size() == 0)
            return ((double)a[tar.first] + a[tar.second]) / 2;

        int l = 0, r = a.size()-1;
        while (l < r) {
            int mid = (l+r) >> 1;
            auto p = findrank(a, b, a[mid]);
            printf("%d %d %d %d\n", mid, a[mid], p.first, p.second);
            if (inbound(p, tar.first)) {
                // puts("FUCK1");
                double ax = a[mid], bx = inbound(p, tar.second) ? ax : findnext(a, b, mid);
                return (ax + bx) / 2;
            } else if (inbound(p, tar.second)) {
                if (n % 2)
                    return a[mid];
                double ax = a[mid], bx = inbound(p, tar.first) ? ax : findprev(a, b, mid);
                return (ax + bx) / 2;
            } else if (p.second <= tar.first)
                l = mid + 1; 
            else
                r = mid - 1;
        }
        int mid = l;
        auto p = findrank(a, b, a[mid]);
        printf("%d %d %d %d\n", mid, a[mid], p.first, p.second);
        if (inbound(p, tar.first)) {
            // puts("FUCK1");
            double ax = a[mid], bx = inbound(p, tar.second) ? ax : findnext(a, b, mid);
            return (ax + bx) / 2;
        } else if (inbound(p, tar.second)) {
            if (n % 2)
                return a[mid];
            double ax = a[mid], bx = inbound(p, tar.first) ? ax : findprev(a, b, mid);
            return (ax + bx) / 2;
        }
        return findMedianSortedArrays(b, a);
    }
};

int main(int argc, char const *argv[])
{
    vector<int> v1 = {1, 2, 4, 5}, v2 = {3};
    Solution s;
    cout << s.findMedianSortedArrays(v1, v2) << endl;
    return 0;
}